<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.10.0"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Direct3D 12 Memory Allocator: Linear allocation algorithm</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr id="projectrow">
  <td id="projectalign">
   <div id="projectname">Direct3D 12 Memory Allocator
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.10.0 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(function() { init_search(); });
});
/* @license-end */
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="index.html">D3D12 Memory Allocator</a></li>  </ul>
</div>
</div><!-- top -->
<div><div class="header">
  <div class="headertitle"><div class="title">Linear allocation algorithm</div></div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>Each D3D12 memory block managed by this library has accompanying metadata that keeps track of used and unused regions. By default, the metadata structure and algorithm tries to find best place for new allocations among free regions to optimize memory usage. This way you can allocate and free objects in any order.</p>
<p><img src="../gfx/Linear_allocator_1_algo_default.png" alt="Default allocation algorithm" class="inline"/></p>
<p>Sometimes there is a need to use simpler, linear allocation algorithm. You can create custom pool that uses such algorithm by adding flag <a class="el" href="namespace_d3_d12_m_a.html#a919d8545365d6b7209a964f2b99936d1aa37a0103f511954ea42a1d0bba286b6a" title="Enables alternative, linear allocation algorithm in this pool.">D3D12MA::POOL_FLAG_ALGORITHM_LINEAR</a> to <a class="el" href="struct_d3_d12_m_a_1_1_p_o_o_l___d_e_s_c.html#ac4ed93b0191344d68c0b4ac1a4822ff4" title="Flags.">D3D12MA::POOL_DESC::Flags</a> while creating <a class="el" href="class_d3_d12_m_a_1_1_pool.html" title="Custom memory pool.">D3D12MA::Pool</a> object. Then an alternative metadata management is used. It always creates new allocations after last one and doesn't reuse free regions after allocations freed in the middle. It results in better allocation performance and less memory consumed by metadata.</p>
<p><img src="../gfx/Linear_allocator_2_algo_linear.png" alt="Linear allocation algorithm" class="inline"/></p>
<p>With this one flag, you can create a custom pool that can be used in many ways: free-at-once, stack, double stack, and ring buffer. See below for details. You don't need to specify explicitly which of these options you are going to use - it is detected automatically.</p>
<h1><a class="anchor" id="linear_algorithm_free_at_once"></a>
Free-at-once</h1>
<p>In a pool that uses linear algorithm, you still need to free all the allocations individually by calling <code>allocation-&gt;Release()</code>. You can free them in any order. New allocations are always made after last one - free space in the middle is not reused. However, when you release all the allocation and the pool becomes empty, allocation starts from the beginning again. This way you can use linear algorithm to speed up creation of allocations that you are going to release all at once.</p>
<p><img src="../gfx/Linear_allocator_3_free_at_once.png" alt="Free-at-once" class="inline"/></p>
<p>This mode is also available for pools created with <a class="el" href="struct_d3_d12_m_a_1_1_p_o_o_l___d_e_s_c.html#abbce3a99f253928f9c3c09fa16015f9e" title="Maximum number of heaps (memory blocks) that can be allocated in this pool. Optional.">D3D12MA::POOL_DESC::MaxBlockCount</a> value that allows multiple memory blocks.</p>
<h1><a class="anchor" id="linear_algorithm_stack"></a>
Stack</h1>
<p>When you free an allocation that was created last, its space can be reused. Thanks to this, if you always release allocations in the order opposite to their creation (LIFO - Last In First Out), you can achieve behavior of a stack.</p>
<p><img src="../gfx/Linear_allocator_4_stack.png" alt="Stack" class="inline"/></p>
<p>This mode is also available for pools created with <a class="el" href="struct_d3_d12_m_a_1_1_p_o_o_l___d_e_s_c.html#abbce3a99f253928f9c3c09fa16015f9e" title="Maximum number of heaps (memory blocks) that can be allocated in this pool. Optional.">D3D12MA::POOL_DESC::MaxBlockCount</a> value that allows multiple memory blocks.</p>
<h1><a class="anchor" id="linear_algorithm_double_stack"></a>
Double stack</h1>
<p>The space reserved by a custom pool with linear algorithm may be used by two stacks:</p>
<ul>
<li>First, default one, growing up from offset 0.</li>
<li>Second, "upper" one, growing down from the end towards lower offsets.</li>
</ul>
<p>To make allocation from the upper stack, add flag <a class="el" href="namespace_d3_d12_m_a.html#abbad31a7e0b3d09d77f3fb704b77645eafb0e2dacce691336e717550a1df72474">D3D12MA::ALLOCATION_FLAG_UPPER_ADDRESS</a> to <a class="el" href="struct_d3_d12_m_a_1_1_a_l_l_o_c_a_t_i_o_n___d_e_s_c.html#a92dec49b788a334fc91c55340dfbace6" title="Flags.">D3D12MA::ALLOCATION_DESC::Flags</a>.</p>
<p><img src="../gfx/Linear_allocator_7_double_stack.png" alt="Double stack" class="inline"/></p>
<p>Double stack is available only in pools with one memory block - <a class="el" href="struct_d3_d12_m_a_1_1_p_o_o_l___d_e_s_c.html#abbce3a99f253928f9c3c09fa16015f9e" title="Maximum number of heaps (memory blocks) that can be allocated in this pool. Optional.">D3D12MA::POOL_DESC::MaxBlockCount</a> must be 1. Otherwise behavior is undefined.</p>
<p>When the two stacks' ends meet so there is not enough space between them for a new allocation, such allocation fails with usual <code>E_OUTOFMEMORY</code> error.</p>
<h1><a class="anchor" id="linear_algorithm_ring_buffer"></a>
Ring buffer</h1>
<p>When you free some allocations from the beginning and there is not enough free space for a new one at the end of a pool, allocator's "cursor" wraps around to the beginning and starts allocation there. Thanks to this, if you always release allocations in the same order as you created them (FIFO - First In First Out), you can achieve behavior of a ring buffer / queue.</p>
<p><img src="../gfx/Linear_allocator_5_ring_buffer.png" alt="Ring buffer" class="inline"/></p>
<p>Ring buffer is available only in pools with one memory block - <a class="el" href="struct_d3_d12_m_a_1_1_p_o_o_l___d_e_s_c.html#abbce3a99f253928f9c3c09fa16015f9e" title="Maximum number of heaps (memory blocks) that can be allocated in this pool. Optional.">D3D12MA::POOL_DESC::MaxBlockCount</a> must be 1. Otherwise behavior is undefined.</p>
<h1><a class="anchor" id="linear_algorithm_additional_considerations"></a>
Additional considerations</h1>
<p>Linear algorithm can also be used with <a class="el" href="virtual_allocator.html">Virtual allocator</a>. See flag <a class="el" href="namespace_d3_d12_m_a.html#a578329923a103be086ac52e3bed2085dabd9968af113acc9a756254ab9f1dc13d" title="Enables alternative, linear allocation algorithm in this virtual block.">D3D12MA::VIRTUAL_BLOCK_FLAG_ALGORITHM_LINEAR</a>. </p>
</div></div><!-- contents -->
</div><!-- PageDoc -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by&#160;<a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.10.0
</small></address>
</body>
</html>
